package leetcode.leetcode142;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/18
 *
 * 检测是否有环，如果有则返回入口
 */
public class Leetcode142 {


    public ListNode detectCycle(ListNode head) {
        ListNode h = head; // 兔子
        ListNode t = head; // 乌龟
        // 兔子每次走两步，乌龟每次走一步，如果兔子和乌龟相遇，则说明有环
        while (h != null && h.next != null) {
            t = t.next;
            h = h.next.next;
            if (t == h) {
                // 进入第二阶段
                /*
                从它们第一次相遇开始，🐢回到起点，🐰保持原位不变
                🐢和🐰一次都走一步，再次相遇时，地点就是环的入口
                 */
                t = head;
                while (true) {
                    if (t == h) {
                        return h;
                    }
                    t = t.next;
                    h = h.next;
                }
            }
        }
        return null;

    }

}
